package sort;
//插入排序
public class InsertSort {

	public static void main(String[] args) {
		int[] a={5,2,9,3,10,1,15,2,6,7,19,50,69,100,150,160,132,169};
		for (int i : a) {
			System.out.print(i+" ");
		}
		sort(a);
	}
	public static void sort(int[] a){
		int i,j;  //都是用来计数的
		System.out.println();
		//首先将最小的元素放到数组中的第一个元素
		for(i=a.length-1;i>=1;i--){
			if(a[i]<a[i-1]){
				 int temp=a[i-1];
				 a[i-1]=a[i];
				 a[i]=temp;
			 }
		}
		//对元素进行插入排序
		for (i = 2; i < a.length; i++) {
			//用j将i的值存储起来
			j = i;
			int temp=a[i];   //存储a[i]的值
			//如果a[i]比a[j]大说明本来就是排序的，无需操作
			//若小的话，则一直移动j，并且将aj的值变为aj-1（即向后移动），最后直到a[i]的值比a[j-1]要大
			//注意这个条件中不能是a[i]<a[j-1],因为当计算第一次aj=aj-1的时候，ai的值就已经改变了
			while(temp<a[j - 1]) {
				a[j]=a[j-1];
				j--;
			}
			a[j]=temp;//当直到a[i]的值比a[j-1]要大，则a[j]的值就是a[i]的值
		}
		for (int k: a) {
			System.out.print(k+" ");
		}
	}
	//交换两个值
	public static void swap(int a,int b){
		int temp=a;
		a=b;
		b=temp;
	}
}
